#include "IndexManager.h"
#include <map>

void sortData(unsigned int b[], int k, int num, int d){
    for(int i = num ; i > 1; --i)
        for(int j = 1; j < num; ++j){
            if(b[k+j*d] < b[k+j*d-d]){
                unsigned int tmp;
                for(int t = 0; t < d; ++t){
                    tmp = b[k+j*d-d+t];
                    b[k+j*d-d+t] = b[k+j*d+t];
                    b[k+j*d+t] = tmp;
                }
            }
        }
}

position IndexManager::getNewPosition(){
    if(curPos.second + INDEX_PER_LEN * 2 <= PAGE_INT_NUM){
        curPos = position(curPos.first, curPos.second + INDEX_PER_LEN);
        return curPos;
    }
    else{
        int index;
        BufType buf = dm->getBpm()->getPage(dm->getFileID(), FIRST_DATABASE_PAGE, index);
        dm->getBpm()->markDirty(index);
        curPos = position(buf[DATABASE_PAGE_NEXT_EMPTY_PAGE], 0);
        ++buf[DATABASE_PAGE_NEXT_EMPTY_PAGE];
        return curPos;
    }
}

bool IndexManager::addNode(int key, int value, int pageid)
{
    int index;
    int curPage = pageid;
    BufType buf = dm->getBpm()->getPage(dm->getFileID(), pageid, index);
    if(buf[2] == (1 << 30)){
        position root;
        root = getNewPosition();
        buf[1] = root.first;
        buf[2] = root.second;
        dm->getBpm()->markDirty(index);
        if(curPage != root.first){
            buf = dm->getBpm()->getPage(dm->getFileID(), root.first, index);
            curPage = root.first;
            dm->getBpm()->markDirty(index);
        }
        buf[root.second + INDEX_NODE_NUM] = 1;
        buf[root.second + INDEX_NODE_TYPE] = INDEX_NODE_TYPE_LEAF;
        buf[root.second + INDEX_NODE_FATHER] = root.first;
        buf[root.second + INDEX_NODE_FATHER + 1] = 1 << 30;
        buf[root.second + INDEX_NODE_DATA] = key;
        position valuePos = getNewPosition();
        buf[root.second + INDEX_NODE_DATA + 1] = valuePos.first;
        buf[root.second + INDEX_NODE_DATA + 2] = valuePos.second;
        int value_index, cur_value_page;
        BufType value_buf = dm->getBpm()->getPage(dm->getFileID(), valuePos.first, value_index);
        cur_value_page = valuePos.first;
        dm->getBpm()->markDirty(value_index);
        position newValue = getNewPosition();
        value_buf[valuePos.second + INDEX_VALUE_NEXT] = newValue.first;
        value_buf[valuePos.second + INDEX_VALUE_NEXT + 1] = newValue.second;
        if(newValue.first != cur_value_page){
            value_buf = dm->getBpm()->getPage(dm->getFileID(), newValue.first, value_index);
            cur_value_page = newValue.first;
            dm->getBpm()->markDirty(value_index);
        }
        value_buf[newValue.second + INDEX_VALUE] = value;
        value_buf[newValue.second + INDEX_VALUE_NEXT] = 1 << 30;
        return true;
    }
    else{
        position node, parent;
        node.first = buf[1];
        node.second = buf[2];
        parent.first = buf[1];
        parent.second = 1 << 30;
        while(true){
            if(curPage != node.first){
                buf = dm->getBpm()->getPage(dm->getFileID(), node.first, index);
                curPage = node.first;
            }
            buf[node.second + INDEX_NODE_FATHER] = parent.first;
            buf[node.second + INDEX_NODE_FATHER + 1] = parent.second;
            parent = node;
            if(buf[node.second + INDEX_NODE_TYPE] == INDEX_NODE_TYPE_LEAF) break;
            int k;
            for(int i = 0 ; i < buf[node.second + INDEX_NODE_NUM]; ++i){
                k = node.second + INDEX_NODE_DATA + i*3;
                if(buf[k] <= key && ((i == buf[node.second + INDEX_NODE_NUM] - 1)||buf[k+3] > key))
                    break;
            }
            node.first = buf[k + 1];
            node.second = buf[k + 2];
        }
        int tkey = key, dis;
        int origin_key, new_key;
        position origin_pos, new_pos;
        while(true){
            if(curPage != node.first && node.second != (1 << 30)){
                buf = dm->getBpm()->getPage(dm->getFileID(), node.first, index);
                curPage = node.first;
            }
            if(node.second == (1 << 30)){
                node = getNewPosition();
                if(curPage != node.first){
                    buf = dm->getBpm()->getPage(dm->getFileID(), node.first, index);
                    curPage = node.first;
                    dm->getBpm()->markDirty(index);
                }
                int root_index;
                BufType root_buf = dm->getBpm()->getPage(dm->getFileID(), pageid, root_index);
                dm->getBpm()->markDirty(root_index);
                root_buf[1] = node.first;
                root_buf[2] = node.second;
                buf[node.second+INDEX_NODE_NUM] = 2;
                buf[node.second+INDEX_NODE_TYPE] = INDEX_NODE_TYPE_UP;
                buf[node.second+INDEX_NODE_FATHER] = node.first;
                buf[node.second+INDEX_NODE_FATHER+1] = 1 << 30;
                buf[node.second+INDEX_NODE_DATA] = origin_key;
                buf[node.second+INDEX_NODE_DATA + 1] = origin_pos.first;
                buf[node.second+INDEX_NODE_DATA + 2] = origin_pos.second;
                buf[node.second+INDEX_NODE_DATA + 3] = new_key;
                buf[node.second+INDEX_NODE_DATA + 4] = new_pos.first;
                buf[node.second+INDEX_NODE_DATA + 5] = new_pos.second;
            }
            else if(buf[node.second + INDEX_NODE_TYPE] == INDEX_NODE_TYPE_LEAF){
                int k;
                bool found = false;
                position valuePos;
                for(int i = 0 ; i < buf[node.second + INDEX_NODE_NUM]; ++i){
                    k = node.second + INDEX_NODE_DATA + i*3;
                    if(buf[k] == key){
                        found = true;
                        valuePos.first = buf[k+1];
                        valuePos.second = buf[k+2];
                        break;
                    }
                }
                if(!found){
                    valuePos = getNewPosition();
                    buf[node.second + INDEX_NODE_DATA + buf[node.second + INDEX_NODE_NUM]*3] = tkey;
                    buf[node.second + INDEX_NODE_DATA + buf[node.second + INDEX_NODE_NUM]*3 + 1] = valuePos.first;
                    buf[node.second + INDEX_NODE_DATA + buf[node.second + INDEX_NODE_NUM]*3 + 2] = valuePos.second;
                    ++buf[node.second + INDEX_NODE_NUM];
                    sortData(buf, node.second + INDEX_NODE_DATA, buf[node.second + INDEX_NODE_NUM], 3);
                    dm->getBpm()->markDirty(index);
                    dis = 3;
                }
                int value_index, cur_value_page;
                BufType value_buf = dm->getBpm()->getPage(dm->getFileID(), valuePos.first, value_index);
                cur_value_page = valuePos.first;
                dm->getBpm()->markDirty(value_index);
                while(found && value_buf[valuePos.second + INDEX_VALUE_NEXT] != (1 << 30)){
                    if(valuePos.first != cur_value_page){
                        value_buf = dm->getBpm()->getPage(dm->getFileID(), valuePos.first, value_index);
                        cur_value_page = valuePos.first;
                        dm->getBpm()->markDirty(value_index);
                    }
                    valuePos.first = value_buf[valuePos.second + INDEX_VALUE_NEXT];
                    valuePos.second = value_buf[valuePos.second + INDEX_VALUE_NEXT + 1];
                }
                position newValue = getNewPosition();
                value_buf[valuePos.second + INDEX_VALUE_NEXT] = newValue.first;
                value_buf[valuePos.second + INDEX_VALUE_NEXT + 1] = newValue.second;
                if(newValue.first != cur_value_page){
                    value_buf = dm->getBpm()->getPage(dm->getFileID(), newValue.first, value_index);
                    cur_value_page = newValue.first;
                    dm->getBpm()->markDirty(value_index);
                }
                value_buf[newValue.second + INDEX_VALUE] = value;
                value_buf[newValue.second + INDEX_VALUE_NEXT] = 1 << 30;
            }
            else{
                int k;
                for(int i = 0 ; i < buf[node.second + INDEX_NODE_NUM]; ++i){
                    k = node.second + INDEX_NODE_DATA + i*3;
                    if(buf[k+1] == origin_pos.first && buf[k+2] == origin_pos.second){
                        buf[k] = origin_key;
                        break;
                    }
                }
                buf[node.second + INDEX_NODE_DATA + buf[node.second + INDEX_NODE_NUM]*3] = new_key;
                buf[node.second + INDEX_NODE_DATA + buf[node.second + INDEX_NODE_NUM]*3 + 1] = new_pos.first;
                buf[node.second + INDEX_NODE_DATA + buf[node.second + INDEX_NODE_NUM]*3 + 2] = new_pos.second;
                ++buf[node.second + INDEX_NODE_NUM];
                sortData(buf, node.second + INDEX_NODE_DATA, buf[node.second + INDEX_NODE_NUM], 3);
                dm->getBpm()->markDirty(index);
                dis = 3;
            }
            if(buf[node.second + INDEX_NODE_NUM] <= INDEX_M)
                break;
            else{
                unsigned int rec[INDEX_PER_LEN];
                for(int i = 0; i < INDEX_PER_LEN; ++i)
                    rec[i] = buf[node.second+i];
                buf[node.second+INDEX_NODE_NUM] = INDEX_M/2+1;
                origin_pos = node;
                origin_key = buf[node.second+INDEX_NODE_DATA];
                node = getNewPosition();
                if(curPage != node.first){
                    buf = dm->getBpm()->getPage(dm->getFileID(), node.first, index);
                    curPage = node.first;
                    dm->getBpm()->markDirty(index);
                }
                buf[node.second+INDEX_NODE_NUM] = INDEX_M - INDEX_M/2;
                buf[node.second+INDEX_NODE_TYPE] = rec[INDEX_NODE_TYPE];
                buf[node.second+INDEX_NODE_FATHER] = rec[INDEX_NODE_FATHER];
                buf[node.second+INDEX_NODE_FATHER+1] = rec[INDEX_NODE_FATHER+1];
                for(int i = INDEX_M/2+1; i <= INDEX_M; ++i)
                    for(int j = 0; j < dis; ++j)
                        buf[node.second+INDEX_NODE_DATA+(i-INDEX_M/2-1)*dis+j] = rec[INDEX_NODE_DATA+i*dis+j];
                new_pos = node;
                new_key = buf[node.second+INDEX_NODE_DATA];
                node.first = buf[node.second + INDEX_NODE_FATHER];
                node.second = buf[node.second + INDEX_NODE_FATHER + 1];
            }
        }
        return true;
    }
}

bool IndexManager::deleteNode(int key, int value, int pageid)
{
    std::vector<int> s;
    s.clear();
    int index;
    int curPage = pageid;
    BufType buf = dm->getBpm()->getPage(dm->getFileID(), pageid, index);
    if(buf[2] != (1 << 30)){
        position node, parent;
        node.first = buf[1];
        node.second = buf[2];
        while(true){
            if(curPage != node.first){
                buf = dm->getBpm()->getPage(dm->getFileID(), node.first, index);
                curPage = node.first;
            }
            int k;
            if(buf[node.second + INDEX_NODE_TYPE] == INDEX_NODE_TYPE_LEAF){
                for(int i = 0 ; i < buf[node.second + INDEX_NODE_NUM]; ++i){
                    k = node.second + INDEX_NODE_DATA + i*3;
                    if(buf[k] == key){
                        position valuePos = position(buf[k+1], buf[k+2]);
                        int value_index, cur_value_page;
                        BufType value_buf = dm->getBpm()->getPage(dm->getFileID(), valuePos.first, value_index);
                        cur_value_page = valuePos.first;
                        while(value_buf[valuePos.second + INDEX_VALUE_NEXT] != (1 << 30)){
                            parent = valuePos;
                            valuePos.first = value_buf[valuePos.second + INDEX_VALUE_NEXT];
                            valuePos.second = value_buf[valuePos.second + INDEX_VALUE_NEXT + 1];
                            if(valuePos.first != cur_value_page){
                                value_buf = dm->getBpm()->getPage(dm->getFileID(), valuePos.first, value_index);
                                cur_value_page = valuePos.first;
                                dm->getBpm()->markDirty(value_index);
                            }
                            if(value_buf[valuePos.second + INDEX_VALUE] == value){
                                position next = position(value_buf[valuePos.second + INDEX_VALUE_NEXT], value_buf[valuePos.second + INDEX_VALUE_NEXT + 1]);
                                if(parent.first != cur_value_page){
                                    value_buf = dm->getBpm()->getPage(dm->getFileID(), parent.first, value_index);
                                    cur_value_page = parent.first;
                                    dm->getBpm()->markDirty(value_index);
                                }
                                value_buf[parent.second + INDEX_VALUE_NEXT] = next.first;
                                value_buf[parent.second + INDEX_VALUE_NEXT + 1] = next.second;
                                return true;
                            }
                        }
                        break;
                    }
                }
                break;
            }
            for(int i = 0 ; i < buf[node.second + INDEX_NODE_NUM]; ++i){
                k = node.second + INDEX_NODE_DATA + i*3;
                if(buf[k] <= key && ((i == buf[node.second + INDEX_NODE_NUM] - 1)||buf[k+3] > key))
                    break;
            }
            node.first = buf[k + 1];
            node.second = buf[k + 2];
        }
    }
    return false;
}

std::vector<int> IndexManager::searchKey(int key,int pageid)
{
    std::vector<int> s;
    s.clear();
    int index;
    int curPage = pageid;
    BufType buf = dm->getBpm()->getPage(dm->getFileID(), pageid, index);
    if(buf[2] != (1 << 30)){
        position node;
        node.first = buf[1];
        node.second = buf[2];
        while(true){
            if(curPage != node.first){
                buf = dm->getBpm()->getPage(dm->getFileID(), node.first, index);
                curPage = node.first;
            }
            int k;
            if(buf[node.second + INDEX_NODE_TYPE] == INDEX_NODE_TYPE_LEAF){
                for(int i = 0 ; i < buf[node.second + INDEX_NODE_NUM]; ++i){
                    k = node.second + INDEX_NODE_DATA + i*3;
                    if(buf[k] == key){
                        position valuePos = position(buf[k+1], buf[k+2]);
                        int value_index, cur_value_page;
                        BufType value_buf = dm->getBpm()->getPage(dm->getFileID(), valuePos.first, value_index);
                        cur_value_page = valuePos.first;
                        while(value_buf[valuePos.second + INDEX_VALUE_NEXT] != (1 << 30)){
                            valuePos.first = value_buf[valuePos.second + INDEX_VALUE_NEXT];
                            valuePos.second = value_buf[valuePos.second + INDEX_VALUE_NEXT + 1];
                            if(valuePos.first != cur_value_page){
                                value_buf = dm->getBpm()->getPage(dm->getFileID(), valuePos.first, value_index);
                                cur_value_page = valuePos.first;
                            }
                            s.push_back(value_buf[valuePos.second + INDEX_VALUE]);
                        }
                        break;
                    }
                }
                break;
            }
            for(int i = 0 ; i < buf[node.second + INDEX_NODE_NUM]; ++i){
                k = node.second + INDEX_NODE_DATA + i*3;
                if(buf[k] <= key && ((i == buf[node.second + INDEX_NODE_NUM] - 1)||buf[k+3] > key))
                    break;
            }
            node.first = buf[k + 1];
            node.second = buf[k + 2];
        }
    }
    return s;
}
